package com.lw.leetcode.linked.b;

/**
 * 707. 设计链表
 *
 * @Author liw
 * @Date 2021/10/30 21:19
 * @Version 1.0
 */
public class MyLinkedList {

    public static void main(String[] args) {
        MyLinkedList test = new MyLinkedList();

        // ["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]
        //[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]
        test.addAtHead(7);
        test.addAtHead(2);
        test.addAtHead(1);
        test.addAtIndex(3, 0);
        test.deleteAtIndex(2);
        test.addAtHead(6);
        test.addAtTail(4);
        System.out.println(test.get(4));
    }

    private ListNode root;
    private ListNode end;
    private int length;

    public MyLinkedList() {
        root = new ListNode(0);
        end = new ListNode(0);
        root.next = end;
        end.prev = root;
    }

    public int get(int index) {
        if (index < 0 || index >= length) {
            return -1;
        }
        return getNode(index).val;
    }

    public void addAtHead(int val) {
        ListNode item = new ListNode(val);
        item.next = root.next;
        root.next.prev = item;
        root.next = item;
        item.prev = root;
        length++;
    }

    public void addAtTail(int val) {
        ListNode item = new ListNode(val);
        item.prev = end.prev;
        end.prev.next = item;
        end.prev = item;
        item.next = end;
        length++;
    }

    public void addAtIndex(int index, int val) {
        if (index > length) {
            return;
        }

        if (index < 0) {
            addAtHead(val);
        } else if (length == index) {
            addAtTail(val);
        } else {
            ListNode item = new ListNode(val);
            ListNode prev = getNode(index).prev;
            item.next = prev.next;
            prev.next.prev = item;
            prev.next = item;
            item.prev = prev;
            length++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) {
            return;
        }
        ListNode prev = getNode(index).prev;
        ListNode next = prev.next.next;
        prev.next = next;
        next.prev = prev;
        length--;
    }

    private ListNode getNode(int index) {
        if (index <= length - index - 1) {
            ListNode item = root;
            while (index >= 0) {
                item = item.next;
                index--;
            }
            return item;
        } else {
            ListNode item = end;
            index = length - index - 1;
            while (index >= 0) {
                item = item.prev;
                index--;
            }
            return item;
        }
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        ListNode(int x) {
            val = x;
        }
    }

}




